题解 CF1360E@洛谷 | 1360E@Codeforces 【Polygon】

拿到这题一头雾水,找找规律。

按照游戏规则,一个数的右侧和下侧必须有数才可能被大炮发射到这里。

看到样例,发现如果去掉最后一行以及最后一列,剩余的所有 11 的右侧或下侧的格子有 11,就是可以完成;反之不能。

大胆猜测:除了最右列与最下行,如果每个 11 右侧或下侧都有 11,则可以完成;有一个 11 右侧下侧均没有 11 就不能完成。

考试时直接交了,没有证明正确性,发现 PP 了。现在口胡一个,不是特别严谨,可以画画图试着理解:

  • 如果一个 11 右侧有 11,可以通过左侧大炮发射过来。
  • 如果一个 11 下侧有 11,可以通过上方大炮发射过来。
  • 最右列和最下行一定可以达到。

类似数学归纳法的思想,证明上面的猜测。

代码:

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;

int T, n, a[55][55];

int main() {
	scanf("%d", &T);
	while(T--) {
		scanf("%d", &n);
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				char c = getchar();
				while(!isdigit(c)) c = getchar();
				a[i][j] = c - '0';
			}
		}
		bool book = true;
		for(int i=1;i<n;i++) {
			for(int j=1;j<n;j++) {
				if(a[i][j] && !a[i][j+1] && !a[i+1][j]) {
					book = false;
					break;
				}
			}
			if(!book) break;
		}
		if(book) puts("YES");
		else puts("NO");
	}
	return 0;
}